/**
 * @author 徐楠
 * @date 2022/4/29 21:57
 * @version 1.0
 */

package com.xunan.likou;

import java.util.Stack;

public class AUniqueSubstringInAWrapString {
    public static void main(String[] args) {
        /*String s = "cccc";
        int substringInWraproundString = findSubstringInWraproundStringPlus(s);
        System.out.println(substringInWraproundString);

        int x = 'c' - 'A';
        System.out.println(x);
        System.out.println((char) x);
        System.out.println();*/

        String aaaaccccbbbdui = removeDuplicateLetters2("aaaazzccccbbbduiaaaz");
        System.out.println(aaaaccccbbbdui);
    }

    /**
     * 我们只需要统计以当前字符结尾的子串即可
     * 最后直接进行求和即可
     * 例如"zab"，假设用cur表示以当前字符结尾的环绕子串个数，当当前字符为'z'时，我们找到一个子串，current = 1，
     * 当当前字符为'a',我们发现和'z'是连续的，current直接加1得，current = 2，而总的子串就有1 + 2 = 3，
     * 当当前字符为'b'和前面的"za"构成连环绕连续，cur再加1，current = 3，而总的环绕子串就有1 + 2 + 3 = 6，
     * 共6个，和题目示例三相同
     * 注意以当前字符为结尾的环绕子串的长度要取最大的，而不是求和，这样不会出现重复子串，
     * 例如"bab",第一个'b'为1,当第二个'b'时，和前面的'a'构成了环绕，
     * 所以为2，而应该是1和2中取最大的2，而不是1 + 2，这样以'b'结尾的子串共有'b'和'ab'两个
     */
    public static int findSubstringInWraproundStringPlus(String p) {
        int[] counts = new int[26];
        int n = p.length();
        int current = 1;
        for (int i = 0; i < n; i++) {
            //判断前一个是否在后一个前面，如果不是就说明是循环字符串得重新计数
            if (i > 0 && (p.charAt(i - 1) - 'a' + 1) % 26 == (p.charAt(i) - 'a') % 26) {
                current++;
            } else {
                current = 1;
            }
            int index = p.charAt(i) - 'a';
            counts[index] = Math.max(counts[index], current);
        }
        int result = 0;
        for (int i : counts) {
            result += i;
        }
        return result;
    }


    public static int findSubstringInWraproundString(String p) {
        String s = removeDuplicateLetters1(p);
        System.out.println(p);
        System.out.println(s);
        int n = s.length();
        if (s.length() > 2 && p.charAt(0) == p.charAt(p.length() - 1)) {
            return n + n * (n - 1) * 1 / 2 - 1;
        }
        /**
         * 求字符串中非空子串的数量
         * 用等差数列求和
         * 因为字符串中每增加一个字母 它嫩构成的子串数 是前一个字母嫩构成的子串数 +1
         * 如 abc
         *              a   b(构成b,ab)   c(构成c,bc,abc)
         * 构成子串数     1       2              3
         */
        return n + n * (n - 1) * 1 / 2;

    }

    /**
     * 用栈去除重复字母
     */
    public static String removeDuplicateLetters1(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.contains(c)) {
                continue;
            }
            //如果栈非空，栈顶元素大于当前字符，且栈顶元素在字符串后面出现，则去掉
            while (!stack.isEmpty() && c < stack.peek() && s.indexOf(stack.peek(), i) != -1) {
                stack.pop();
            }
            stack.push(c);
        }
        char[] str = new char[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            str[i] = stack.get(i);
        }
        return new String(str);
    }


    /**
     * 用数组去除重复字母
     */
    public static String removeDuplicateLetters2(String s) {
        boolean[] res = new boolean[26];
        int[] num = new int[26];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!res[c - 'a']) {
                while (sb.length() > 0 && c < sb.charAt(sb.length() - 1)) {
                    //后面还存在此元素
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        res[sb.charAt(sb.length() - 1) - 'a'] = false;
                        //不添加了，删除掉，之后 再添加，因为后面还存在此元素
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                res[c - 'a'] = true;
                sb.append(c);
            }
            num[c - 'a'] -= 1;
        }
        return sb.toString();
    }

}
